Index mapping (or direct addressing, or a trivial
hash function
A hash function is any function that can be used to map data of arbitrary size to fixed-size values. The values returned by a hash function are called ''hash values'', ''hash codes'', ''digests'', or simply ''hashes''. The values are usually u ...
) in
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
describes using an
array
An array is a systematic arrangement of similar objects, usually in rows and columns.
Things called an array include:
{{TOC right
Music
* In twelve-tone and serial composition, the presentation of simultaneous twelve-tone sets such that the ...
, in which each position corresponds to a key in the
universe
The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the universe. Acc ...
of possible values.
The technique is most effective when the universe of keys is reasonably small, such that
allocating an array with one position for every possible key is affordable.
Its effectiveness comes from the fact that an arbitrary position in an array can be examined in
constant time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
.
Applicable arrays
There are many practical examples of data whose valid values are restricted within a small range. A trivial hash function is a suitable choice when such data needs to act as a lookup key. Some examples include:
*
month in the year (1–12)
*
day in the month (1–31)
*
day of the week
In many languages, the names given to the seven days of the week are derived from the names of the classical planets in Hellenistic astronomy, which were in turn named after contemporary deities, a system introduced by the Sumerians and la ...
(1–7)
* human age (0–130) – e.g. lifecover actuary tables, fixed-term mortgage
*
ASCII
ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because of ...
characters (0–127), encompassing common mathematical operator symbols, digits, punctuation marks, and English language alphabet
Examples
Using a trivial hash function, in a non-iterative table lookup, can eliminate conditional testing and branching completely, reducing the
instruction path length
In computer performance, the instruction path length is the number of machine code instructions required to execute a section of a computer program. The total path length for the entire program could be deemed a measure of the algorithm's performa ...
of a computer program.
Avoid branching
Roger Sayle gives an example
of eliminating a
multiway branch Multiway branch is the change to a program's control flow based upon a value matching a selected criteria. It is a form of conditional statement. A multiway branch is often the most efficient method of passing control to one of a set of program l ...
caused by a
switch statement:
inline bool HasOnly30Days(int m)
Which can be replaced with a table lookup:
inline bool HasOnly30Days(int m)
See also
*
Associative array
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an ...
*
Hash table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
*
Lookup table
References
{{Reflist
Arrays
Associative arrays
Articles with example C code
*
Search algorithms